import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: liangyuanzhang
 * Date: 2025-3-22
 * Time: 10:06
 */
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList2 = new LinkedList<>();
        linkedList2.add(1);//默认都是尾插
        linkedList2.addLast(3);
        linkedList2.addLast(4);
        linkedList2.addLast(5);
        System.out.println(linkedList2);

        System.out.println("===== ListIterator ====");
        ListIterator<Integer> lit2 =  linkedList2.listIterator(linkedList2.size());
        while (lit2.hasPrevious()) {
            System.out.print(lit2.previous()+" ");
        }
        System.out.println();

        System.out.println("===== ListIterator ====");
        ListIterator<Integer> lit =  linkedList2.listIterator();
        while (lit.hasNext()) {
            System.out.print(lit.next()+" ");
        }
        System.out.println();

        System.out.println("===== Iterator ====");
        Iterator<Integer> it = linkedList2.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();


        System.out.println("=====for each====");

        for(Integer x : linkedList2) {
            System.out.print(x +" ");
        }
        System.out.println();

        System.out.println("=====for====");
        for (int i = 0; i < linkedList2.size(); i++) {
            System.out.print(linkedList2.get(i) +" ");
        }
        System.out.println();


    }
    public static void main6(String[] args) {
        List<Integer> linkedList1 = new LinkedList<>();
        LinkedList<Integer> linkedList2 = new LinkedList<>();
        linkedList2.add(1);//默认都是尾插
        linkedList2.addFirst(2);
        linkedList2.addLast(3);
        linkedList2.addLast(4);
        linkedList2.addLast(5);
        System.out.println(linkedList2);

        ArrayList<Integer> list = new ArrayList<>();
        list.add(11);
        list.add(21);
        list.add(31);

        linkedList2.addAll(list);

        System.out.println(linkedList2);

        linkedList2.remove(2);
        System.out.println(linkedList2);

    }


    public static void main5(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);

        myLinkedList.display();

        myLinkedList.clear();
        //myLinkedList.addIndex(3,9);
        myLinkedList.display();

    }












    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode headA,
                                                      MySingleList.ListNode headB) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;
        //遍历这2个链表
        while (headA != null && headB != null) {
            if(headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if(headA != null) {
            tmp.next = headA;
        }
        if(headB != null) {
            tmp.next = headB;
        }
        return newHead.next;
    }

    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,
                                                            MySingleList.ListNode headB) {
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        //1.先求2个链表的长度
        int lenA = 0;
        int lenB = 0;
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        //2. 求一下差值
        int len = lenA -lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB -lenA;
        }
        //走完上述2步，pl一定指向最长的链表 ps 一定指向最短的链表
        // 接下来的操作 只需要操作 pl  和 ps 就行了
        //3. 让最长的链表 走len步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        //4.两个引用同时走 直到他们相遇
        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null) {
            return null;//没相交
        }
        return pl;
    }

    public static void createCut(MySingleList.ListNode headA,
                                 MySingleList.ListNode headB) {
        headB.next.next.next = headA.next.next;
    }

    public static void main4(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(11);
        list.addLast(21);
        list.addLast(31);
        list.addLast(41);
        list.addLast(51);
        list.createLoop();
        System.out.println(list.hasCycle());
        MySingleList.ListNode ret = list.detectCycle();
        System.out.println(ret.val);
    }

    public static void main3(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(11);
        list.addLast(21);
        list.addLast(31);
        list.addLast(41);
        list.addLast(51);

        MySingleList list2 = new MySingleList();
        list2.addLast(12);
        list2.addLast(23);
        list2.addLast(34);
        list2.addLast(45);
        list2.addLast(56);

        createCut(list.head, list2.head);

        MySingleList.ListNode ret = getIntersectionNode(list.head, list2.head);
        System.out.println(ret.val);
    }

    public static void main2(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(11);
        list.addLast(21);
        list.addLast(31);
        list.addLast(41);
        list.addLast(51);

        MySingleList list2 = new MySingleList();
        list2.addLast(12);
        list2.addLast(23);
        list2.addLast(34);
        list2.addLast(45);
        list2.addLast(56);

        MySingleList.ListNode newH = mergeTwoLists(list.head,list2.head);

        list2.display2(newH);
    }

    public static void main1(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(5);
        list.display();
        MySingleList.ListNode ret = list.middleNode();
        System.out.println(ret.val);

        /*MySingleList.ListNode ret = list.reverseList();
        list.display2(ret);*/

        /*list.remove(3);
        list.display();
        System.out.println("==============");
        list.clear();
        list.display();*/

        /*list.createList();
        list.display();*/
        /*list.addFirst(99);
        list.addFirst(12);
        list.addFirst(23);
        list.addFirst(34);
        list.display();
        list.addIndex(0,199);
        list.addIndex(1,299);
        list.addIndex(6,699);
        list.display();*/
        //System.out.println(list.size());
    }
}
